#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
	int count = 0;

	int findTargetSumWays(vector<int>& nums, int target) {
		backtrack(nums, target, 0, 0);
		return count;
	}

	void backtrack(vector<int>& nums, int target, int index, int sum) {
		if (index == nums.size()) {
			if (sum == target) {
				count++;
			}
		}
		else {
			backtrack(nums, target, index + 1, sum + nums[index]);
			backtrack(nums, target, index + 1, sum - nums[index]);
		}
	}
};

void main() {
	vector<int> nums = { 1,1,1,1,1 };
	Solution s;
	int res=s.findTargetSumWays(nums, 3);
	cout << res << endl;
} 